\documentclass[10pt]{article}
\usepackage{amsmath}

\newcommand{\problem}[1]{\noindent{\sc Problem #1.}}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\complexity}{\noindent{\sc Complexity. }}
\newcommand{\answer}{\noindent{\sc Answer. }}

\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}

\problem{340}
Crazy Function.

For fixed integers $a, b, c$, define the \emph{crazy function} $F(n)$ as follows:
\[
F(n) = n - c \text{ for all } n > b
\]
\[
F(n) = F(a + F(a + F(a + F(a + n)))) \text{ for all } n \le b.
\]
Also, define $S(a, b, c) = \sum_{n=0}^b F(n)$.

For example, if $a = 50$, $b = 2000$ and $c = 40$, then $F(0) = 3240$ and $F(2000) = 2040$.
Also, $S(50, 2000, 40) = 5204240$.

Find the last 9 digits of $S(21^7, 7^{21}, 12^7)$.

\solution

We work out an explicit formula for $F(n)$ backwards, i.e. from $n=b$ to $n=0$. Note that in the following derivation, it is critical that $a \ge c$; otherwise the problem will become much more complicated. After some investigation, we find that $F(n)$ is piecewise linear. Denote $F(n) \equiv F_k(n)$ over the interval
\[
b-(k+1)a < n \le b-ka
\]
Below we show that
\[
F_k(n) = (n+ka) + (4+3k)(a-c) .
\]

We start with the case when $k=0$. Then $b-a < n \le b$, so $a+n > b$, so we have $F(a+n) = n+(a-c)$. Since by assumption $a \ge c$, so $F(a+n) \ge n$. It follows that $a+F(a+n) \ge a+n > b$, so $F(a+F(a+n)) = n+2(a-c)$. Using similar arguments, we find $F_0(n) = n+4(a-c)$, which proves the case for $k=0$.

Now suppose that the proposition holds for $k$, we want to prove it for $k+1$. For $F_{k+1}(n)$, we have by definition
\[
b-(k+2)a < n \le b-(k+1)a,
\]
which is equivalent to
\[
b-(k+1)a < a+n \le b-ka.
\]
Therefore,
\[
F(a+n) = F_k(a+n) = [n+(k+1)a] + (4+3k)(a-c)
\]
Since by assumption $a \ge c$, we have
\[
a+F(a+n) \ge n+(k+2)a > b,
\]
therefore
\[
F(a+F(a+n)) = F(a+n) + (a-c).
\]
Using similar arguments, we find
\[
F(n) = F(a+n) + 3(a-c) = [n+(k+1)a] + [4+3(k+1)](a-c)
\]
So the case is proved for $k+1$.

To find the sum of the first $b$ terms of $F(n)$, we compute it over each piecewise line segment. Let $S_k(m)$ denote the sum of the last $m$ elements of $F_k(n)$, and let $d=a-c$. Then
\begin{align}
S_k(m) &= \sum_{n=b-ka-m+1}^{b-ka} F_k(n) \notag \\
&= \sum_{n=b-ka-m+1}^{b-ka} (n+ka) + (4+3k)d \notag \\
&= \frac{ [(b-ka-m+1)+(b-ka)]m }{2} + [ka+(4+3k)d]m \notag \\
&= 3dmk + (b+4d)m - \frac{m(m-1)}{2} \notag
\end{align}
Finally, let $l = \lfloor (b+1)/a \rfloor$ denote the number of full line segments, and $r = b+1-la$ denote the number of remaining elements in the first line segment that covers $F_l(0)$. Then we have
\begin{align}
S(a,b,c) &= S_l(r) + \sum_{k=0}^{l-1} S_k(a) \notag \\
&= 3drl + (b+4d)r - \frac{r(r-1)}{2} \notag \\
&+ \frac{3da(l-1)l}{2} + \left[ (b+4d)a - \frac{a(a-1)}{2} \right]l \notag
\end{align}

\answer
$S(21^7, 7^{21}, 12^7) \equiv 291504964 \,\, (\text{mod } 1000000000)$

\complexity

Time complexity: $\mathcal{O}(1)$

Space complexity: $\mathcal{O}(1)$

\end{document}
